4 7
0 0 200
0 1 300
1 2 150
1 3 250
2 4 350
2 5 100
3 6 400
3
0 100 1
1 150 2
2 200 3
6
0 0 6 100
1 1 3 150
2 2 5 80
3 4 0 200
4 3 6 120
5 5 1 50